Skip to main content

Leetcode 670 Maximum Swap

· 3 min read

給一正整數, 任意挑選其中最多(可不選)兩個數字交換位置, 回傳其最大值

Problem

Medium

You are given an integer num. You can swap two digits at most once to get the maximum valued number.

Return the maximum valued number you can get.

Example 1:

Input: num = 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

Example 2:

Input: num = 9973
Output: 9973
Explanation: No swap.

Constraints:

  • 0 <= num <= 10**8

My Solution

time: O(n), space: O(n)​

class Solution(object):
    def maximumSwap(self, num):
        n = [int(x) for x in str(num)]
        l = len(n)
        d = [None] * l
        d[-1] = l-1
        maxi = l-1
        for i in range(l-1, -1, -1):
            if n[i] > n[maxi]:
                maxi = i
            d[i] = maxi
        for i in range(l):
            if i != d[i] and n[i] != n[d[i]]:
                return num - (10**(l-1-i) - 10**(l-1-d[i])) * (n[i] - n[d[i]])
        return num

with comment​

class Solution(object):
    def maximumSwap(self, num):
        n = [int(x) for x in str(num)]
        l = len(n)

        # use O(n) space
        d = [None] * l
        d[-1] = l-1
        maxi = l-1

        # iterate foward, find index of max value
        for i in range(l-1, -1, -1):
            if n[i] > n[maxi]:
                maxi = i
            d[i] = maxi

        # e.g.
        #    * *
        # 012345 <- index of n
        # 987123 <- value of n
        #    v v
        # -------
        #    *
        # 987333 <- max value of n (foward)
        # 012555 <- index of max value of n (foward)
        #    *

        # the two index:   i  &   d[i]
        # the two value: n[i] & n[d[i]]
        for i in range(l):
            if i != d[i] and n[i] != n[d[i]]:
                # caculate the result
                # return num - (10**(l-1-i) - 10**(l-1-d[i])) * (n[i] - n[d[i]])
                # or swap in the list
                n[i], n[d[i]] = n[d[i]], n[i]
                # then join and cast them
                return int(''.join(str(x) for x in n))

        # no swap
        return num

減少空間 & one pass​

class Solution(object):
    def maximumSwap(self, num):
        n = list(str(num))
        l = len(n)
        left = right = maxi = l-1
        for i in range(l-1, -1, -1):
            if n[i] > n[maxi]:
                maxi = i
            elif n[i] != n[maxi]:
                left, right = i, maxi
        n[left], n[right] = n[right], n[left]
        return int(''.join(x for x in n))